package mo.offer_special;

import mo.common.Node;

public class L028 {


    public Node flatten(Node head) {
        dfs(head);
        return head;
    }

    private Node dfs(Node node) {
        Node cur = node;
        Node last = null; //需要记录链表的尾节点

        while (cur != null) {
            Node next = cur.next;
            if (cur.child != null) {
                Node childLast = dfs(cur.child);
                next = cur.next;

                cur.next = cur.child;
                cur.child.prev = cur;

                if (next != null) {
                    childLast.next = next;
                    next.prev = childLast;
                }

                cur.child = null;
                last = childLast;
            } else {
                last = cur;
            }
            cur = next;
        }

        return last;
    }

    public static void main(String[] args) {
        L028 test = new L028();
        Node node1 = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        Node node4 = new Node(4);
        node1.next = node2;
        node2.prev = node1;
        node1.child = node3;
        node3.child = node4;
        Node res = test.flatten(node1);
        System.out.println(res);
    }

}
